//二叉树的层序遍历
/*给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr)
            return ret;
        queue<TreeNode*> Queue;
        Queue.push(root);
        while(Queue.size()) {
            int cur_count = Queue.size();
            ret.push_back({});
            for (int i = 1; i <= cur_count; i++) {
                TreeNode* temp = Queue.front();
                ret.back().push_back(temp->val);
                Queue.pop();
                if (temp->left)
                    Queue.push(temp->left);
                if (temp->right)
                    Queue.push(temp->right);
            }
        }
        return ret;
    }
};

//LCR 084. 全排列 II 
/*给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
1 <= nums.length <= 8
-10 <= nums[i] <= 10
*/
class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool hash[8] = {0};

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums);
        return ret;
    }
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size();) {
            if (hash[i] == false) {
                path.push_back(nums[i]);
                hash[i] = true;
                dfs(nums);
                path.pop_back();
                hash[i] = false;
                i++;
                while (i < nums.size() && nums[i] == nums[i - 1])
                    i++;
            } else
                i++;
        }
    }
};

//电话号码的字母组合
/*给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
*/
class Solution {
    vector<string> ret;
    string path;
    vector<string> tele = {{""},    {""},    {"abc"},  {"def"}, {"ghi"},
                           {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"}};

public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty())
        return ret;
        dfs(digits, 0);
        return ret;
    }
    void dfs(string& digits, int pos) {
        if (path.size() == digits.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < tele[digits[pos] - '0'].size(); i++) {
            path.push_back(tele[digits[pos] - '0'][i]);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};